package main

import (
	"bytes"
	"fmt"
	"io"
	"math"
	"os"
	"strings"
)

var M = math.Inf(1)

type Graph [][]float64

func (g Graph) ShortestDist(start, end int) float64 {
	return g[start][end]
}

func (d Graph) checkCycleOfNegative() (exist bool) {
	n := len(d)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			for t := 0; t < n; t++ {
				if d[i][t] < M && d[t][t] < 0 && d[t][j] < M {
					d[i][j] = -M
					exist = true
				}
			}
		}
	}
	return
}

func (g Graph) Clone() Graph {
	n := len(g)
	g1 := make(Graph, n)
	for i := 0; i < n; i++ {
		g1[i] = make([]float64, n)
		for j := 0; j < n; j++ {
			g1[i][j] = g[i][j]
		}
	}
	return g1
}

func (g Graph) String() string {
	sb := new(bytes.Buffer)
	sb.WriteString(fmt.Sprintf("%3s", ""))
	for i := range g {
		sb.WriteString(fmt.Sprintf("%6s", nodeNames[i]))
	}
	sb.WriteString("\n")
	for i, row := range g {
		if i > 0 {
			sb.WriteString("\n")
		}
		sb.WriteString(fmt.Sprintf("%-3s", nodeNames[i]))
		//sb.WriteString("[")
		for _, d := range row {
			if d == M {
				sb.WriteString(fmt.Sprintf("%6s", "∞"))
			} else if d == -M {
				sb.WriteString(fmt.Sprintf("%6s", "-∞"))
			} else {
				sb.WriteString(fmt.Sprintf("%6.0f", d))
			}
		}
		//sb.WriteString("]")
	}
	return sb.String()
}

type Path []int

func (p Path) String() string {
	sb := new(strings.Builder)
	for i, node := range p {
		if i > 0 {
			sb.WriteString("->")
		}
		sb.WriteString(nodeNames[node])
	}
	return sb.String()
}

type GraphPath [][]int

func (gp GraphPath) String() string {
	sb := new(bytes.Buffer)
	sb.WriteString(fmt.Sprintf("%-3s", ""))
	for i := range gp {
		sb.WriteString(fmt.Sprintf("%-5s", nodeNames[i]))
	}
	sb.WriteString("\n")
	for i, p := range gp {
		if i > 0 {
			sb.WriteString("\n")
		}
		sb.WriteString(fmt.Sprintf("%-3s", nodeNames[i]+"|"))
		//sb.WriteString("[")
		for _, node := range p {
			if node == -1 {
				sb.WriteString(fmt.Sprintf("%-5s", "-"))
			} else {
				sb.WriteString(fmt.Sprintf("%-5s", nodeNames[node]))
			}
		}
		//sb.WriteString("]")
	}
	return sb.String()
}

func (gp GraphPath) ShortestPath(start, end int) (p Path) {
	p = make([]int, len(gp))
	i := len(gp) - 1
	p[i] = end
	for pri := gp[start][end]; pri != -1 && i > 0; pri = gp[start][pri] {
		i--
		p[i] = pri
	}
	if i > 0 && p[i] != start {
		i--
		p[i] = start
	}
	p = p[i:]
	if p[0] != start {
		dst := make([]int, len(p)+1)
		dst[0] = start
		copy(dst[1:], p)
		p = dst
	}
	return
}

// 返回g对应的距离图d，g本身不做任何改变
func floyd(g Graph) (d Graph, p GraphPath) {
	d = g.Clone()
	n := len(d)
	p = make([][]int, n)
	for i := 0; i < n; i++ {
		p[i] = make([]int, n)
		for j := 0; j < n; j++ {
			//默认 -1 ，节点不通
			p[i][j] = -1
			//相邻节点有直接的前驱节点（排除自身节点）
			if d[i][j] != M && i != j {
				p[i][j] = i
			}
		}
	}

	//	for t := 0; t < n; t++ {
	//		for i := 0; i < n; i++ {
	//			for j := 0; j < n; j++ {
	// 一定是，且必须是，代表中间点的节点t写在for循环第一行，只有for第一行的节点才表示中间点，这三行for代码顺序不可置换，并非是变量含义，而是for代码行的位置决定了节点意义，比如第一行就决定了意义是中间节点，这才代表了Floyd算法的插点法
	//
	//
	for t := 0; t < n; t++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if d[i][t] < M && d[t][j] < M {
					//if d[t][t] < 0 {
					//	d[i][j] = -M
					//}
					if d[i][t]+d[t][j] < d[i][j] {
						d[i][j] = d[i][t] + d[t][j]
						p[i][j] = p[t][j] // i->j 虚拟路径经过节点k（实际路径最终也会经过节点k），所以i->j的前驱节点同样也是k->j虚拟路径的前驱节点
					}
				}
			}
		}
	}
	return
}

var nodeNames = map[int]string{
	0:  "A",
	1:  "B",
	2:  "C",
	3:  "D",
	4:  "E",
	5:  "F",
	6:  "G",
	7:  "H",
	-1: "-",
}

var nodeIndex = map[string]int{
	"A": 0,
	"B": 1,
	"C": 2,
	"D": 3,
	"E": 4,
	"F": 5,
	"G": 6,
	"H": 7,
	"-": -1,
}

// 负权环.png
var g1 = Graph{
	//A B  C  D  E  F  G  H
	{0, 2, 4, 7, M, M, M, M},  //A
	{2, 0, M, M, -4, 8, M, 1}, //B
	{4, M, 0, -3, M, M, M, M}, //C
	{7, M, -3, 0, 1, 3, M, M}, //D
	{M, -4, M, 1, 0, M, 1, M}, //E
	{M, 8, M, 3, M, 0, M, M},  //F
	{M, M, M, M, 1, M, 0, 1},  //G
	{M, 1, M, M, M, M, 1, 0},  //H
}

// 根据 负权环.png 改装，将初始 B->E, C->D 的来回权值总和改为非负权值（可以等于零）
// 负权环_v0.png
var g1_v0 = Graph{
	//A B  C  D  E  F  G  H
	{0, 1, 4, 7, M, M, M, M},  //A
	{1, 0, M, M, -4, 9, M, 1}, //B
	{4, M, 0, -3, M, M, M, M}, //C
	{7, M, 3, 0, 1, 3, M, M},  //D
	{M, 5, M, 1, 0, M, 1, M},  //E
	{M, 9, M, 3, M, 0, M, M},  //F
	{M, M, M, M, 1, M, 0, 2},  //G
	{M, 1, M, M, M, M, 2, 0},  //H
}

// =============== 用于调试，明白其中原理 ===============
// 负权环2.png
var g2 = Graph{
	//A B  C
	{0, 7, 4},  //A
	{7, 0, -3}, //B
	{4, -3, 0}, //C
}

// 有负权值但无负权环.png
var g3 = Graph{
	//A B  C
	{0, 7, 4},  //A
	{7, 0, -3}, //B
	{4, 4, 0},  //C
}

// =============== 用于调试，明白其中原理 ===============

func main() {
	g := g1_v0.Clone()
	fmt.Println("==== Graph ====")
	fmt.Println(g)
	d, p := floyd(g)
	fmt.Println("==== Distance ====")
	fmt.Println(d)
	fmt.Println("==== Path ====")
	fmt.Println(p)
	fmt.Println()

	if d.checkCycleOfNegative() {
		fmt.Println("存在负权环，便没有最短路径")
		fmt.Println(d)
		return
	}

	var startNode, endNode string
	for {
		fmt.Print("请输入起始节点名字：")
		_, err := fmt.Scanf("%s %s\n", &startNode, &endNode)
		if err != nil {
			if err == io.EOF {
				break
			}
			fmt.Fprintln(os.Stderr, "输入错误，", err)
			continue
		}
		startNode = strings.ToUpper(startNode)
		start, ok := nodeIndex[startNode]
		if !ok {
			fmt.Println("\t该图中没有【起点】节点：", startNode)
			continue
		}
		endNode = strings.ToUpper(endNode)
		end, ok := nodeIndex[endNode]
		if !ok {
			fmt.Println("\t该图中没有【终点】节点：", endNode)
			continue
		}
		fmt.Printf("%s->%s:%.0f，最短路径：%s\n", nodeNames[start], nodeNames[end], d.ShortestDist(start, end), p.ShortestPath(start, end))
	}
}
